"""
递归结束条件：
    如果其中一个数组为空，直接返回另一个数组

递归操作：
    如果l1.val < l2.val，则l1.next = (l1.next, l2)
    返回l1
    否则                   l2.next = (l1, l2.next)
    返回l2
"""


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2

        if not l2:
            return l1

        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
#############################
"""
首先，创建一个dummy烧饼节点，初始化p1,p2指针分别指向l1,l2，cur节点指向dummy

然后，如果p1指针元素<=p2指针元素，cur.next连接到p1节点，并更新p1、cur指针
    否则，p1指针元素>p2指针元素，cur.next连接到p2节点，并更新p2、cur指针

接下来，某一个指针还存在，cur.next连接到存在指针p1或p2

最后，返回dummy下一个节点
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import List


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        
        dummy = ListNode(-1)
        p1, p2, cur = l1, l2, dummy

        while p1 and p2:
            if p1.val <= p2.val:
                cur.next = p1
                p1 = p1.next
                cur = cur.next
            else:
                cur.next = p2
                p2 = p2.next
                cur = cur.next
        
        cur.next = p1 if p2 is None else p2
        return dummy.next